1. Field of the Invention
This invention relates to digital data communication, and more particularly to an improved ,method and apparatus for encoding and decoding packet switching communication to provide improved efficiency in processing non-sequentially transmitted data packets.
2. Description of the Background Art
Data encoding and decoding are functions that ensure the privacy of a digital communication by preventing an unauthorized receiver from understanding the contents of a transmitted message. Examples of encoding include encrypting plaintext data into ciphertext using an invertable encryption function, compressing plaintext data by adding compression codes or equations, and altering plaintext data via an invertable mathematical algorithm. Decoding is the inverse of encoding and includes decrypting encoded data to recover the original plaintext data, or decompressing compressed data by applying a decompressing code or equation to regain the full data string.
U.S. patent application Ser. No. 08/110,402 entitled "Method and Apparatus for Variable Overhead Cached Encryption" filed Aug. 23, 1993 discloses a digital encryption structure that allows the computational overhead associated with digital encryption to be varied by selectively reusing a pseudorandom encoding sequence at the transmitter end and by storing and reusing pseudorandom decoding sequences at the receiver end.
Ser. No. 08/184,978, entitled "Method and Apparatus for Improving the Security of an Electronic Codebook Encryption Scheme Utilizing an Offset in the Pseudorandom Sequence" filed Jan. 21, 1994 addresses utilizing a randomly generated offset in the pseudorandom encoding sequence to vary the starting point at which the pseudorandom encoding sequence is combined with the plaintext data to produce the ciphertext.
Ser. No. 08/193,248, entitled "Method and Apparatus for Improving the Security of an Electronic Codebook Encryption Scheme Utilizing a Data Dependent Encryption Function" filed Feb. 8, 1994 improves upon the security of an electronic codebook encryption scheme by further including a mapping table in the encoder. A byte of ciphertext and a random number byte associated with each byte of plaintext data are exchanged to change the relationships within the mapping table. An inverse mapping table, a table that is the inverse of the encoder's mapping table, is included in the receiver. Imported encrypted communication is separated and exchanged in the inverse mapping table to produce unencrypted plaintext data identical to that originally encoded.
Generally, in the conventional processing of packet switching communication, encoded data packets are transmitted through a packet switching network to a receiver where they are received and stored in a memory. When all available encoded data packets are received, the receiver first sorts the stored packets into sequential order and then decodes them in a second step. The decoded packets are then exported to an intended receiver.
Referring now to FIG. 1, a diagram is shown of a typical prior art system for encoding and decoding streamlined, sequentially transmitted data. In the system of FIG. 1, a transmitter receives and encodes sequences of plaintext data and transmits the encoded data through a packet switching network to a receiver where the data is decoded. Plaintext data is commonly divided up into data packets, with each data packet consisting of a portion of the plaintext data sequence. The transmitter is comprised of an encoding function generator and an encoder, where the encoding function generator provides an encoding sequence or encoding function to the encoder. In a streaming mode, the plaintext data is received as data packets by the encoder and is there combined with the encoding sequence to produce encoded data. The resultant encoded packets are then transmitted to the receiver through the packet switching network, where they are decoded using a method that is the inverse of that used for data encoding by the transmitter. As the packets travel through the network, the encoded packets travel individually along many different paths. Thus, not all of the encoded packets will reach the receiver at the same time or in the original streaming mode sequence. The receiver is comprised of a memory, a decoding function generator and a decoder. The receiver imports the encoded packets from the network and first stores the encoded packets in the memory. Each encoded packet is placed in the memory storage in its arranged position with respect to the sequential order of the encoded data. When all available encoded packets are received, they are then processed by the decoder. The sequentially ordered encoded data packets are combined in the decoder with a decoding sequence from the decoding function generator to produce decoded data which is the same as the originally encoded plaintext data. The decoded data is then exported from the receiver.
In the conventional decoding process of the prior art, the encoded data packets imported by the receiver are first stored and sorted in the memory. Decoding of the stored packets does not commence until all of the packets have been received and sorted. Storing the imported encoded packets in the memory prior to decoding causes an undesirable delay in the final transmission of the data to the intended receiver. Another drawback of the conventional processing scheme is that, because the encoded packets are stored in the receiver's memory prior to being decoded, a very large memory is required in order to process long messages.
What is needed is a packet switching communication system that decodes and exports encoded data as soon as the data is received, without the need for extensive data storage and unnecessary delay.